package com.example.gustavo.hello;

import com.example.gustavo.hello.activity.MainActivity;

import org.apache.commons.lang3.math.IEEE754rUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created by gustavo on 2015/8/5.
 */
public class QuestionTest {


    public static void main(String[] args) {

//        ArrayPrint arrayPrint = new ArrayPrint();
//        arrayPrint.printArray(5);
//        arrayPrint.display();


        PriorityQueue<String> pq = new PriorityQueue<>(5);
        pq.add("apple");
        pq.add("google");
        pq.add("lenovo");
        pq.add("dell");
        pq.add("nokia");
        String s = pq.toString();
        System.out.println("s = " + s);

        while (!pq.isEmpty()) {
            String poll = pq.poll();
            System.out.println("poll = " + poll);
        }

    }

    /**
     * You are climbing a stair case. It takes n steps to reach to the top.
     * <p>
     * Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
     */
    public static int climbStairs(int n) {

        if (n <= 2) return n;
        //递归 效率太低
//        return climbStairs(n -2) + climbStairs(n -1);

        /*int[] count = new int[n];
        count[0] = 1;
        count[1] = 2;*/

        int first = 1;
        int second = 2;


        for (int i = 0; i < n; i++) {
//            count[i] = count[i - 2] + count[i -1];

            second = first + second;
            first = second - first;
        }

        return second;


    }

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode(int x) { val = x; }
     * }
     */
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    /**
     * Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
     * <p>
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode(int x) { val = x; }
     * }
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        PriorityQueue pq = new PriorityQueue(lists.length, new Comparator<ListNode>() {
            @Override
            public int compare(ListNode lhs, ListNode rhs) {
                return lhs.val - rhs.val;
            }
        });

        for (ListNode node : lists) {
            if (node != null)
                pq.add(node);
        }

        ListNode head = new ListNode(0);
        ListNode p = head;

        while (!pq.isEmpty()) {
            ListNode node = (ListNode) pq.poll();
            if (node.next != null)  pq.add(node.next);
            p.next = node;
            p = p.next;
        }

        return head.next;


    }

    /**
     * Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
     * For example,
     * Given n = 3,
     * <p>
     * You should return the following matrix:
     * [
     * [ 1, 2, 3 ],
     * [ 8, 9, 4 ],
     * [ 7, 6, 5 ]
     * ]
     */
    public static void spiralMatrix(int n) {

        int[][] result = new int[n][n];
        /*int start = 1;
        for (int index = 0; index < n; index++) {
            if (start > n * n) break;
            int length = n - index * 2;

            for (int i = 0; i < length; i++) {//上横列
                result[index][i + index] = start++;

            }
            for (int i = 1; i < length; i++) {//右竖列
                result[i + index][length + index - 1] = start++;
            }
            for (int i = length - 2; i >= 0; i--) {//下横列
                result[length + index - 1][index + i] = start++;
            }
            for (int i = length - 2; i > 0; i--) {//左竖列
                result[index + i][index] = start++;
            }
        }*/


        int flag = 0;
        int dir = 1;
        int up = n;
        int right = n - 1;
        int down = n - 1;
        int left = n - 2;
        int row = 0, column = -1;

        for (int i = 1; i <= n * n; i++) {

            switch (dir) {

                case 1:
                    flag++;
                    column++;

                    if (flag == up) {

                        dir = 2;
                        flag = 0;
                        up -= 2;

                    }

                    break;

                case 2:
                    flag++;
                    row++;

                    if (flag == right) {
                        dir = 3;
                        flag = 0;
                        right -= 2;
                    }

                    break;

                case 3:
                    flag++;
                    column--;
                    if (flag == down) {
                        dir = 4;
                        flag = 0;
                        down -= 2;
                    }

                    break;

                case 4:
                    flag++;
                    row--;

                    if (flag == left) {

                        dir = 1;
                        flag = 0;
                        left -= 2;
                    }

                    break;

            }
            result[row][column] = i;
        }

        /*System.out.println("[");
        for (int j = 0; j < result.length; j++) {

                System.out.print("  [");
                for (int i = 0; i < result[j].length; i++) {

                    if(i == result[j].length - 1){

                        System.out.print(result[j][i] );
                    }else{
                        System.out.print(result[j][i] + " ,");
                    }
                }
            if(j == result.length - 1){

                System.out.println("]");
            }else{

                System.out.println("],");
            }
        }
        System.out.println("]");*/


    }

    public static class ArrayPrint {
        int[][] aa;
        int start = 1;

        /*递归调用*/
        public void makeArray(int num, int index) {
            if (start > num * num) return;
            //index 从0开始，把数组圈分成4部分
            int length = num - index * 2;
            for (int i = 0; i < length; i++) {//上横列
                aa[index][i + index] = start++;

            }
            for (int i = 1; i < length; i++) {//右竖列
                aa[i + index][length + index - 1] = start++;
            }
            for (int i = length - 2; i >= 0; i--) {//下横列
                aa[length + index - 1][index + i] = start++;
            }
            for (int i = length - 2; i > 0; i--) {//左竖列
                aa[index + i][index] = start++;
            }
        }

        public void display() {
            for (int i = 0; i < aa.length; i++) {
                int[] str = aa[i];
                for (int j = 0; j < str.length; j++) {
                    System.out.print(str[j] + ",");
                }
                System.out.println("");
            }
        }

        public void printArray(int num) {
            aa = new int[num][num];
            for (int i = 0; i < num; i++) {
                makeArray(num, i);
            }
        }

        public static void main(String args[]) {
            ArrayPrint ap = new ArrayPrint();
            ap.printArray(10);
            ap.display();
        }
    }
}
